package com.gitee.wsl.lang.array

import com.gitee.wsl.ext.array.binarySearch
import com.gitee.wsl.ext.array.minSize
import kotlin.jvm.JvmOverloads
import kotlin.math.min

/**
 * `SparseArray` maps integers to Objects and, unlike a normal array of Objects,
 * its indices can contain gaps. `SparseArray` is intended to be more memory-efficient
 * than a
 * [`HashMap`](/reference/java/util/HashMap), because it avoids
 * auto-boxing keys and its data structure doesn't rely on an extra entry object
 * for each mapping.
 *
 *
 * Note that this container keeps its mappings in an array data structure,
 * using a binary search to find keys. The implementation is not intended to be appropriate for
 * data structures
 * that may contain large numbers of items. It is generally slower than a
 * `HashMap` because lookups require a binary search,
 * and adds and removes require inserting
 * and deleting entries in the array. For containers holding up to hundreds of items,
 * the performance difference is less than 50%.
 *
 *
 * To help with performance, the container includes an optimization when removing
 * keys: instead of compacting its array immediately, it leaves the removed entry marked
 * as deleted. The entry can then be re-used for the same key or compacted later in
 * a single garbage collection of all removed entries. This garbage collection
 * must be performed whenever the array needs to be grown, or when the map size or
 * entry values are retrieved.
 *
 *
 * It is possible to iterate over the items in this container using
 * [.keyAt] and [.valueAt]. Iterating over the keys using
 * `keyAt(int)` with ascending values of the index returns the
 * keys in ascending order. In the case of `valueAt(int)`, the
 * values corresponding to the keys are returned in ascending order.
 */
open class SparseArray<E>(
    initialCapacity: Int = 0,
    private val sThrowExceptionForUpperArrayOutOfBounds:Boolean = false
) {
    private var mGarbage = false

    private var mKeys: IntArray

    private var mValues: kotlin.Array<Any?>

    private var mSize: Int

    /**
     * Creates a new SparseArray containing no mappings that will not
     * require any additional memory allocation to store the specified
     * number of mappings.  If you supply an initial capacity of 0, the
     * sparse array will be initialized with a light-weight representation
     * not requiring any additional array allocations.
     */
    /**
     * Creates a new SparseArray containing no mappings.
     */
    init {
        if (initialCapacity == 0) {
            mKeys = IntArray(0)
            mValues = arrayOfNulls<Any>(0)
        } else {
            mValues = arrayOfNulls<Any>(initialCapacity)
            mKeys = IntArray(mValues.size)
        }
        mSize = 0
    }

   /*
   override fun clone(): SparseArray<E> {
        var clone: SparseArray<E>? = null
        try {
            clone = super.clone() as SparseArray<E>
            clone.mKeys = mKeys.clone()
            clone.mValues = mValues.clone()
        } catch (cnse: java.lang.CloneNotSupportedException) {
            *//* ignore *//*
        }
        return clone!!
    }
    */

    /**
     * Returns true if the key exists in the array. This is equivalent to
     * [.indexOfKey] >= 0.
     *
     * @param key Potential key in the mapping
     * @return true if the key is defined in the mapping
     */
    operator fun contains(key: Int): Boolean {
        return indexOfKey(key) >= 0
    }

    private fun getRawIndex(key: Int) = mKeys.binarySearch(key, toIndex = mSize).index

    /**
     * Gets the Object mapped from the specified key, or the specified Object
     * if no such mapping has been made.
     */
    /**
     * Gets the Object mapped from the specified key, or `null`
     * if no such mapping has been made.
     */
    @JvmOverloads
    operator fun get(key: Int, valueIfKeyNotFound: E? = null): E? {
        val i: Int = getRawIndex(key)

        return if (i < 0 || mValues[i] === DELETED) {
            valueIfKeyNotFound
        } else {
            mValues[i] as E?
        }
    }

    fun get(key: Int, valueIfKeyNotFound: (key:Int) -> E? ): E? {
        val i: Int = getRawIndex(key)
        val ret = mValues[i]
        return if (i < 0 ||  ret === DELETED || ret ==null) {
            valueIfKeyNotFound(key)
        } else {
            mValues[i] as E
        }
    }

    /**
     * Removes the mapping from the specified key, if there was any.
     */
    fun delete(key: Int) {
        val i: Int = getRawIndex(key)

        if (i >= 0) {
            if (mValues[i] !== DELETED) {
                mValues[i] = DELETED
                mGarbage = true
            }
        }
    }

    /**
     * @hide
     * Removes the mapping from the specified key, if there was any, returning the old value.
     */
    fun removeReturnOld(key: Int): E? {
        val i: Int = getRawIndex(key)

        if (i >= 0) {
            if (mValues[i] !== DELETED) {
                val old = mValues[i] as E?
                mValues[i] = DELETED
                mGarbage = true
                return old
            }
        }
        return null
    }

    /**
     * Alias for [.delete].
     */
    fun remove(key: Int) {
        delete(key)
    }

    /**
     * Removes the mapping at the specified index.
     *
     *
     * For indices outside of the range `0...size()-1`,
     * the behavior is undefined for apps targeting [android.os.Build.VERSION_CODES.P] and
     * earlier, and an [ArrayIndexOutOfBoundsException] is thrown for apps targeting
     * [android.os.Build.VERSION_CODES.Q] and later.
     */
    fun removeAt(index: Int) {
        if (index >= mSize && sThrowExceptionForUpperArrayOutOfBounds) {
            // The array might be slightly bigger than mSize, in which case, indexing won't fail.
            // Check if exception should be thrown outside of the critical path.
            throw IndexOutOfBoundsException(index.toString())
        }
        if (mValues[index] !== DELETED) {
            mValues[index] = DELETED
            mGarbage = true
        }
    }

    /**
     * Remove a range of mappings as a batch.
     *
     * @param index Index to begin at
     * @param size Number of mappings to remove
     *
     *
     * For indices outside of the range `0...size()-1`,
     * the behavior is undefined.
     */
    fun removeAtRange(index: Int, size: Int) {
        val end = min(mSize.toDouble(), (index + size).toDouble()).toInt()
        for (i in index until end) {
            removeAt(i)
        }
    }

    private fun gc() {
        // Log.e("SparseArray", "gc start with " + mSize);

        val n = mSize
        var o = 0
        val keys = mKeys
        val values = mValues

        for (i in 0 until n) {
            val `val` = values[i]

            if (`val` !== DELETED) {
                if (i != o) {
                    keys[o] = keys[i]
                    values[o] = `val`
                    values[i] = null
                }

                o++
            }
        }

        mGarbage = false
        mSize = o

        // Log.e("SparseArray", "gc end with " + mSize);
    }

    /**
     * Alias for [.put] to support Kotlin [index]= operator.
     * @see .put
     */
    operator fun set(key: Int, value: E) {
        put(key, value)
    }

    /**
     * Adds a mapping from the specified key to the specified value,
     * replacing the previous mapping from the specified key if there
     * was one.
     */
    fun put(key: Int, value: E) {
        var i: Int = getRawIndex(key)

        if (i >= 0) {
            mValues[i] = value
        } else {
            i = i.inv()

            if (i < mSize && mValues[i] === DELETED) {
                mKeys[i] = key
                mValues[i] = value
                return
            }

            if (mGarbage && mSize >= mKeys.size) {
                gc()

                // Search again because indices may have changed.
                i = getRawIndex(key).inv()
            }

            appendAndGrowing(key,value)
            mSize++
        }
    }

    /**
     * Returns the number of key-value mappings that this SparseArray
     * currently stores.
     */
    fun size(): Int {
        if (mGarbage) {
            gc()
        }

        return mSize
    }

    /**
     * Given an index in the range `0...size()-1`, returns
     * the key from the `index`th key-value mapping that this
     * SparseArray stores.
     *
     *
     * The keys corresponding to indices in ascending order are guaranteed to
     * be in ascending order, e.g., `keyAt(0)` will return the
     * smallest key and `keyAt(size()-1)` will return the largest
     * key.
     *
     *
     * For indices outside of the range `0...size()-1`,
     * the behavior is undefined for apps targeting [android.os.Build.VERSION_CODES.P] and
     * earlier, and an [ArrayIndexOutOfBoundsException] is thrown for apps targeting
     * [android.os.Build.VERSION_CODES.Q] and later.
     */
    fun keyAt(index: Int): Int {
        if (index >= mSize && sThrowExceptionForUpperArrayOutOfBounds) {
            // The array might be slightly bigger than mSize, in which case, indexing won't fail.
            // Check if exception should be thrown outside of the critical path.
            throw  IndexOutOfBoundsException(index.toString())
        }
        if (mGarbage) {
            gc()
        }

        return mKeys[index]
    }

    /**
     * Given an index in the range `0...size()-1`, returns
     * the value from the `index`th key-value mapping that this
     * SparseArray stores.
     *
     *
     * The values corresponding to indices in ascending order are guaranteed
     * to be associated with keys in ascending order, e.g.,
     * `valueAt(0)` will return the value associated with the
     * smallest key and `valueAt(size()-1)` will return the value
     * associated with the largest key.
     *
     *
     * For indices outside of the range `0...size()-1`,
     * the behavior is undefined for apps targeting [android.os.Build.VERSION_CODES.P] and
     * earlier, and an [ArrayIndexOutOfBoundsException] is thrown for apps targeting
     * [android.os.Build.VERSION_CODES.Q] and later.
     */
    fun valueAt(index: Int): E? {
        if (index >= mSize && sThrowExceptionForUpperArrayOutOfBounds) {
            // The array might be slightly bigger than mSize, in which case, indexing won't fail.
            // Check if exception should be thrown outside of the critical path.
            throw  IndexOutOfBoundsException(index.toString())
        }
        if (mGarbage) {
            gc()
        }

        return mValues[index] as E?
    }

    /**
     * Given an index in the range `0...size()-1`, sets a new
     * value for the `index`th key-value mapping that this
     * SparseArray stores.
     *
     *
     * For indices outside of the range `0...size()-1`, the behavior is undefined for
     * apps targeting [android.os.Build.VERSION_CODES.P] and earlier, and an
     * [ArrayIndexOutOfBoundsException] is thrown for apps targeting
     * [android.os.Build.VERSION_CODES.Q] and later.
     */
    fun setValueAt(index: Int, value: E) {
        if (index >= mSize && sThrowExceptionForUpperArrayOutOfBounds) {
            // The array might be slightly bigger than mSize, in which case, indexing won't fail.
            // Check if exception should be thrown outside of the critical path.
            throw  IndexOutOfBoundsException(index.toString())
        }
        if (mGarbage) {
            gc()
        }

        mValues[index] = value
    }

    /**
     * Returns the index for which [.keyAt] would return the
     * specified key, or a negative number if the specified
     * key is not mapped.
     */
    fun indexOfKey(key: Int): Int {
        if (mGarbage) {
            gc()
        }

        return getRawIndex(key)
    }

    /**
     * Returns an index for which [.valueAt] would return the
     * specified value, or a negative number if no keys map to the
     * specified value.
     *
     * Beware that this is a linear search, unlike lookups by key,
     * and that multiple keys can map to the same value and this will
     * find only one of them.
     *
     * Note also that unlike most collections' `indexOf` methods,
     * this method compares values using `==` rather than `equals`.
     */
    fun indexOfValue(value: E): Int {
        if (mGarbage) {
            gc()
        }

        for (i in 0 until mSize) {
            if (mValues[i] === value) {
                return i
            }
        }

        return -1
    }

    /**
     * Returns an index for which [.valueAt] would return the
     * specified value, or a negative number if no keys map to the
     * specified value.
     *
     * Beware that this is a linear search, unlike lookups by key,
     * and that multiple keys can map to the same value and this will
     * find only one of them.
     *
     * Note also that this method uses `equals` unlike `indexOfValue`.
     * @hide
     */
    fun indexOfValueByValue(value: E?): Int {
        if (mGarbage) {
            gc()
        }

        for (i in 0 until mSize) {
            if (value == null) {
                if (mValues[i] == null) {
                    return i
                }
            } else {
                if (value == mValues[i]) {
                    return i
                }
            }
        }
        return -1
    }

    /**
     * Removes all key-value mappings from this SparseArray.
     */
    fun clear() {
        val n = mSize
        val values = mValues

        for (i in 0 until n) {
            values[i] = null
        }

        mSize = 0
        mGarbage = false
    }

    /**
     * Puts a key/value pair into the array, optimizing for the case where
     * the key is greater than all existing keys in the array.
     */
    fun append(key: Int, value: E) {
        if (mSize != 0 && key <= mKeys[mSize - 1]) {
            put(key, value)
            return
        }

        if (mGarbage && mSize >= mKeys.size) {
            gc()
        }

        appendAndGrowing(key,value)
        mSize++
    }

    private fun appendAndGrowing(key: Int,value:E){
        mKeys = mKeys.minSize(mSize)
        mKeys[mSize] = key
        mValues = mValues.minSize(mSize)
        mValues[mSize] = value
    }

    /**
     * {@inheritDoc}
     *
     *
     * This implementation composes a string by iterating over its mappings. If
     * this map contains itself as a value, the string "(this Map)"
     * will appear in its place.
     */
    override fun toString(): String {
        if (size() <= 0) {
            return "{}"
        }

        val buffer = StringBuilder(mSize * 28)
        buffer.append('{')
        for (i in 0 until mSize) {
            if (i > 0) {
                buffer.append(", ")
            }
            val key = keyAt(i)
            buffer.append(key)
            buffer.append('=')
            val value: Any? = valueAt(i)
            if (value !== this) {
                buffer.append(value)
            } else {
                buffer.append("(this Map)")
            }
        }
        buffer.append('}')
        return buffer.toString()
    }

    /**
     * Compares the contents of this [SparseArray] to the specified [SparseArray].
     *
     * For backwards compatibility reasons, [Object.equals] cannot be implemented,
     * so this serves as a manually invoked alternative.
     */
    fun contentEquals(other: SparseArray<*>?): Boolean {
        if (other == null) {
            return false
        }

        val size = size()
        if (size != other.size()) {
            return false
        }

        // size() calls above took care about gc() compaction.
        for (index in 0 until size) {
            if (mKeys[index] != other.mKeys[index]
                || mValues[index] != other.mValues[index]
            ) {
                return false
            }
        }

        return true
    }

    /**
     * Returns a hash code value for the contents of this [SparseArray], combining the
     * [Objects.hashCode] result of all its keys and values.
     *
     * For backwards compatibility, [Object.hashCode] cannot be implemented, so this serves
     * as a manually invoked alternative.
     */
    fun contentHashCode(): Int {
        var hash = 0
        val size = size()
        // size() call above took care about gc() compaction.
        for (index in 0 until size) {
            val key = mKeys[index]
            val value = mValues[index] as E?
            hash = 31 * hash + key
            hash = 31 * hash + value.hashCode()
        }
        return hash
    }

    companion object {
        private val DELETED = Any()
    }
}